/*
 * @Author: your name
 * @Date: 2021-05-07 10:02:01
 * @LastEditTime: 2021-05-07 17:04:10
 * @LastEditors: LittleSource
 * @Description: In User Settings Edit
 * @FilePath: \arithmetic\dijkstra\dijkstra.go
 */
package dijkstra

import (
	"fmt"
	"math"
)

type Dijkstra struct {
	graph       map[string]map[string]int
	nodeKeyList []string
	parents     map[string]string
	searchedMap map[string]bool
}

/**
 * @description: 狄克斯特拉算法，在加权有向无环图中寻找最“便宜”路线
 * @param {*}
 * @return {*}
 */
func (d *Dijkstra) Run() {
	//初始化储存标记搜索过或未搜索的散列表
	d.searchedMap = make(map[string]bool)
	for i := range d.nodeKeyList {
		d.searchedMap[d.nodeKeyList[i]] = false
	}
	//初始化开销散列表
	costs := make(map[string]int)
	// //获取开始节点的子节点并将其加入开销散列表
	for k, v := range d.graph["start"] {
		costs[k] = v
		//删除节点列表内添加到开销散列表的节点
		d.nodeKeyList = deleteExistKey(d.nodeKeyList, k)
	}
	//将节点列表内剩余节点添加到开销散列表，并初始化开销数据为无穷大
	for i := range d.nodeKeyList {
		//这里有一个知识点，狄克斯特拉算法加权图权必须为正
		costs[d.nodeKeyList[i]] = math.MaxInt64
	}
	//获取未查询过的最便宜的节点
	node := d.findLowestCostNode(costs)
	for node != "" {
		//获取该节点的邻近节点数组
		nearNodes := d.graph[node]
		for k, v := range nearNodes {
			//当前节点的邻近节点的新的开销 = 从开始到达当前节点的开销 + 当前节点到邻近节点的开销
			newCost := costs[node] + v
			//如果当前节点的邻近节点的开销 > 当前节点的邻近节点的新的开销
			if costs[k] > newCost {
				costs[k] = newCost
				d.parents[k] = node
			}
		}
		//将当前节点标记为已查询过
		d.searchedMap[node] = true
		//再获取未查询过的最便宜的节点，继续下次循环
		node = d.findLowestCostNode(costs)
		//fmt.Println(costs)
	}
	fmt.Println("父子节点散列表：")
	fmt.Println(d.parents)
}

/**
 * @description: 从开销散列表中找出开销最小且未查询过的的节点
 * @param {map[string]int} costs 开销散列表
 * @return string 节点键名
 */
func (d *Dijkstra) findLowestCostNode(costs map[string]int) string {
	lowestKey := ""
	lowestValue := math.MaxInt64 //无穷大
	for k, v := range costs {
		if v < lowestValue && !d.searchedMap[k] {
			lowestKey = k
			lowestValue = v
		}
	}
	return lowestKey
}

/**
 * @description: 从字符串数组里删除指定字符串
 * @param {[]string} arr 目标字符串数组
 * @param {string} key 指定的字符串
 * @return {[]string} 删除后的字符串数组
 */
func deleteExistKey(arr []string, key string) []string {
	index := -1
	for i := range arr {
		if arr[i] == key {
			index = i
		}
	}
	if index == -1 {
		return arr
	} else {
		return append(arr[:index], arr[index+1:]...)
	}
}
